We investigate the complexity of counting trees, forests and bases ofmatroids from a parameterized point of view. It turns out that the problems ofcomputing the number of trees and forests with $k$ edges are $\# W[1]$-hardwhen parameterized by $k$. Together with the recent algorithm for deterministicmatrix truncation by Lokshtanov et al. (ICALP 2015), the hardness result for$k$-forests implies $\# W[1]$-hardness of the problem of counting bases of amatroid when parameterized by rank or nullity, even if the matroid isrestricted to be representable over a field of characteristic $2$. Wecomplement this result by pointing out that the problem becomes fixed parametertractable for matroids represented over a fixed finite field.
展开▼
机译：我们从参数化的角度研究计数类树的森林，树木和森林的复杂性。事实证明，计算带有$ k $边缘的树木和森林的数量的问题是$ \＃W [1] $-当由$ k $参数化时。连同Lokshtanov等人最近的确定性矩阵截断算法。 （ICALP 2015），$ k $ -forests的硬度结果暗示了$ \＃W [1] $-通过等级或零值进行参数化时计算无序类的基数的问题的难度，即使拟似类被限制为可以在a上表示$ 2 $的特征字段。通过指出问题，对于在固定有限域上表示的拟阵，该问题变为固定参数可处理的。
展开▼
